package week_06;

import java.util.Arrays;

public class Bag_0_1 {

    public int maxValueBag1(int[][] nums, int m) {
        int n = nums.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = Integer.MIN_VALUE;
        }
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
            }
            int v = nums[i - 1][0];
            int w = nums[i - 1][1];
            for (int j = v; j <= m; j++) {
                System.out.println(dp[i - 1][j - v] + w);
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v] + w);
                //f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            }
        }
        int ans = 0;
        for (int j = 1; j <= m; j++) {
            ans = Math.max(ans, dp[n][j]);
        }
        return ans;
    }


    public int maxValueBag(int[][] nums, int m) {
        int n = nums.length;
        int[] dp = new int[m + 1];
        dp[0]=0;
        for(int i=0;i<n;i++){
            int v = nums[i ][0];
            int w = nums[i ][1];
            for(int j=m;j>=v;j--){
                dp[j]=Math.max(dp[j],dp[j-v]+w);
            }
        }
        int ans = 0;
        for (int j = 1; j <= m; j++) {
            ans = Math.max(ans, dp[j]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{{2, 5}, {1, 2}, {4, 6}};
        Bag_0_1 test = new Bag_0_1();
        test.maxValueBag(arr, 4);
    }
}
